1. 题目

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1\sim2^h$ 个节点。

示例:

输入:

输出: 6

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

一开始用的BFS。

看题解竟然是二分+位运算，有点意思。记下来，以后整合一下。

利用完全二叉树的性质，求出最大深度h，结点的个数的范围即为 $[2^h,2^{h+1}-1]$

在这个范围内二分即可。判定函数要利用位运算。偷张图：

3. 代码

3.1. BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> Q;
        int cnt = 0;
        TreeNode* tmp;
        Q.push(root);
        while(!Q.empty()){
            tmp = Q.front();
            Q.pop();
            cnt ++;
            if(tmp->left) Q.push(tmp->left);
            if(tmp->right) Q.push(tmp->right);
        }
        return cnt;
    }
};

3.2. 二分+位运算

3.2.1. 左开右开

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool C(TreeNode* root, int h, int k){
        k = k & ((1<<h--)-1);//去掉首一

        TreeNode* tmp = root;
        for(int i = h; i >=0 ; --i){
            if(k&(1<<i)) tmp = tmp->right;
            else tmp = tmp->left;
            if(!tmp) return false;
        }
        return true;
    }
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int h = -1;
        TreeNode* tmp = root;
        while(tmp){
            h++;
            tmp = tmp->left;
        }
        int L = (1<<h)-1, R = (1<<(h+1));//左开右开
        while(L+1!=R){
            int mid = (L+R)>> 1;
            if(C(root, h, mid)) L = mid;
            else R = mid; 
        }

        return L;
    }
};

3.2.2. 左闭右开

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool C(TreeNode* root, int h, int k){
        k = k & ((1<<h--)-1);//去掉首一

        TreeNode* tmp = root;
        for(int i = h; i >=0 ; --i){
            if(k&(1<<i)) tmp = tmp->right;
            else tmp = tmp->left;
            if(!tmp) return false;
        }
        return true;
    }
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int h = -1;
        TreeNode* tmp = root;
        while(tmp){
            h++;
            tmp = tmp->left;
        }
        int L = (1<<h), R = (1<<(h+1));//左闭右开
        while(L<R){
            int mid = (L+R)>> 1;
            if(C(root, h, mid)) L = mid+1;
            else R = mid; 
        }

        return L-1;
    }
};

3.2.3. 左闭右闭

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool C(TreeNode* root, int h, int k){
        k = k & ((1<<h--)-1);//去掉首一

        TreeNode* tmp = root;
        for(int i = h; i >=0 ; --i){
            if(k&(1<<i)) tmp = tmp->right;
            else tmp = tmp->left;
            if(!tmp) return false;
        }
        return true;
    }
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int h = -1;
        TreeNode* tmp = root;
        while(tmp){
            h++;
            tmp = tmp->left;
        }
        int L = (1<<h), R = (1<<(h+1))-1;//左闭右闭
        while(L<=R){
            int mid = (L+R)>> 1;
            if(C(root, h, mid)) L = mid+1;
            else R = mid-1; 
        }

        return R;
    }
};

222 完全二叉树的结点个数